      1  /**

      2     The sort method of this class sorts an array, using the quick

      3     sort algorithm.

      4  */

      5  public class QuickSorter

      6  {

      7     /**

      8        Sorts an array, using quick sort.

      9        @param a the array to sort

     10     */

     11     public static void sort(int[] a)

     12     {

     13        sort(a, 0, a.length - 1);

     14     }

     15

     16     /**

     17        Sorts a portion of an array, using quick sort.

     18        @param a the array to sort

     19        @param from the first index of the portion to be sorted

     20        @param to the last index of the portion to be sorted

     21     */

     22     public static void sort(int[] a, int from, int to)

     23     {

     24        if (from >= to) { return; }

     25        int p = partition(a, from, to);

     26        sort(a, from, p);

     27        sort(a, p + 1, to);

     28     }

     29

     30     /**

     31        Partitions a portion of an array.

     32        @param a the array to partition

     33        @param from the first index of the portion to be partitioned

     34        @param to the last index of the portion to be partitioned

     35        @return the last index of the first partition

     36     */

     37     private static int partition(int[] a, int from, int to)

     38     {

     39        int pivot = a[from];

     40        int i = from - 1;

     41        int j = to + 1;

     42        while (i < j)

     43        {

     44           i++; while (a[i] < pivot) { i++; }

     45           j--; while (a[j] > pivot) { j--; }

     46           if (i < j) { ArrayUtil.swap(a, i, j); }

     47        }

     48        return j;

     49     }

     50  }